#include "1myTree.h"
#include <bits/stdc++.h>
string pre;  // 保留前序遍历结果
string ino;  // 保留中序遍历结果
string post; // 保留后序遍历结果相反结果即根，右，左
TreeNode *nownode = (TreeNode *)malloc(sizeof(TreeNode));
TreeNode *Node = (TreeNode *)malloc(sizeof(TreeNode));
using namespace std;
TreeNode::TreeNode(char ch, TreeNode *Lc, TreeNode *Rc, NodeTag LT, NodeTag RT)
{
  this->data = ch;
  this->leftChild = Lc;
  this->rightChild = Rc;
  this->lTag = LT;
  this->rTag = RT;
}
TreeNode::~TreeNode() {}
MyTree::MyTree() // 无参构造
{
  this->isThread = 0; // 初始化一颗空树，使他的线索二叉树标志为零
}
MyTree::MyTree(const char ch[]) // 构造函数，根据二叉树的先序序列，生成二叉树的二叉链表存储,使用@表示NULL
{
  //this->node=ch;//变动
  int il=0;
  for(il=0;ch[il]!='\0';il++)
  {
    node[il]=ch[il];
  }
  node[il]='\0';
  stack<TreeNode *> s; // 运用栈记录前序遍历的左节点，方便去根据结点指向右节点
  this->isThread = 0;  //????
  int i = 0;
  if (ch[i] == '@')
    return;
  TreeNode *p;
  TreeNode *q;
  p = (TreeNode *)malloc(sizeof(TreeNode));
  this->root = p;
  p->data = ch[i];
  i++;
  num = 1; // 结点个数
  while ((ch[i] != '\0') || (!s.empty()))
  {
    if (p == NULL) // p的值为空则读取下一个数值
    {
      i++;
    }
    else // 不断建立左子树，直到遇到“@”即空值
    {
      while (ch[i] != '@')
      {
        q = (TreeNode *)malloc(sizeof(TreeNode));
        q->data = ch[i];
        p->leftChild = q;
        s.push(p); // 将遍历过的父结点记录在栈中
        p = q;
        i++;
        num++;
      }
      p->leftChild = NULL;
      s.push(p);
      i++;
    }
    if (!s.empty())
    {
      p = s.top();
      s.pop(); // 读取栈顶元素，去建立右子树，再以其为根节点去建立树
      if (ch[i] != '@')
      {
        q = (TreeNode *)malloc(sizeof(TreeNode));
        q->data = ch[i];
        p->rightChild = q;
        p = q; // p=p->rightChild;
        i++;
        num++;
      }
      else
      {
        p->rightChild = NULL;
        p = NULL; //????
      }
    }
  }
}
MyTree::MyTree(const MyTree &T) // 拷贝函数
{
  /*this->isThread = 0; // 该函数同样适合线索二叉树s
  if (T.root == NULL)
    return;
  stack<TreeNode *> s1, s2;
  TreeNode *q1;
  q1 = (TreeNode *)malloc(sizeof(TreeNode));
  TreeNode *q2; // q2的作用是一块空间，不断复制T树中的值，连接到q1上
  TreeNode *p;
  p = T.root;      // 用p去遍历树节点
  this->root = q1; // 将树复制到q1中
  q1->data = p->data;
  num = 1; // 结点个数
  while (p != NULL || !s1.empty())
  {
    while (p != NULL)
    {
      s1.push(p);
      s2.push(q1);
      p = p->leftChild;
      if (p != NULL)
      {
        num++;
        q2 = (TreeNode *)malloc(sizeof(TreeNode));
        q2->data = p->data;
        q1->leftChild = q2;
        q1 = q2;
      }
      else
      {
        q1->leftChild = NULL;
      }
      if (!s1.empty())
      {
        p = s1.top();
        q1 = s2.top();
        s1.pop();
        s2.pop();
        p = p->rightChild; // 有改动
        if (p != NULL)
        {
          num++;
          q2 = (TreeNode *)malloc(sizeof(TreeNode));
          q2->data = p->data;
          q1->rightChild = q2;
          q1 = q2;
        }
        else
        {
          q1->rightChild = NULL;
        }
      }
    }
  }*/
  new(this)MyTree(T.node);
}
MyTree::~MyTree() {}            // 析构函数
void MyTree::preOrderTraverse() // 前序遍历
{
  string pre = "\0"; // 保留前序遍历结果
  stack<TreeNode *> s;
  TreeNode *p = root;
  while (p != NULL || !s.empty())
  {
    while (p != NULL)
    {
      pre += p->data;
      cout << p->data;
      s.push(p);
      p = p->leftChild;
    }
    if (!s.empty())
    {
      p = s.top();
      s.pop();
      p = p->rightChild;
    }
  }
}
void MyTree::inOrderTraverse() // 中序遍历
{
  string ino = "\0"; // 保留中序遍历结果
  stack<TreeNode *> s;
  TreeNode *p = root;
  while (p != NULL || !s.empty())
  {
    while (p != NULL)
    {
      s.push(p);
      p = p->leftChild;
    }
    if (!s.empty())
    {
      p = s.top();
      ino += p->data;
      cout << p->data;
      s.pop();
      p = p->rightChild;
    }
  }
}
void MyTree::postOrderTraverse() // 后序遍历
{
  string post = "\0"; // 保留后序相反遍历结果
  stack<TreeNode *> s;
  TreeNode *p = root;
  while (p != NULL || !s.empty())
  {
    while (p != NULL)
    {
      post += p->data;
      s.push(p);
      p = p->rightChild;
    }
    if (!s.empty())
    {
      p = s.top();
      s.pop();
      p = p->leftChild;
    }
  }
  int len = post.size();
  for (int j = len - 1; j >= 0; j--)
  {
    cout << post[j];
  }
}
int MyTree::countLeaf() // 叶结点计数
{
  int sum = 0;
  stack<TreeNode *> s;
  TreeNode *p = root;
  while (p != NULL || !s.empty())
  {
    while (p != NULL)
    {
      s.push(p);
      p = p->leftChild;
    }
    if (!s.empty())
    {
      p = s.top();
      s.pop();
      if ((p->leftChild == NULL) && (p->rightChild == NULL))
        sum++;
      p = p->rightChild; // 不能有else，如果有else会将p点再次入栈
    }
  }
  return sum;
}
int MyTree::height(const TreeNode *root)
{
  int m, n;
  if (root == NULL)
    return 0;
  else
  {
    m = height(root->leftChild);  // 左子树高度
    n = height(root->rightChild); // 右子树高度
  }
  return (m > n) ? m + 1 : n + 1; // 取高的加1
}
int MyTree::countHeight() // 计算树的深度
{
  return height(root);
}
bool MyTree::isThreadedTree() // 判断是否为线索二叉树
{
  return isThread;
}
void MyTree::inThread(TreeNode *root)
{
  TreeNode *rec = NULL; // 前驱
  TreeNode *p = root;
  if (p == NULL)
    return;
  if (p != NULL)
  {
    if (p->leftChild != NULL)
    {
      inThread(p->leftChild); // 递归左子树线索化
    }
    else
      return;
    if (p->leftChild != NULL) //
    {
      p->lTag = Thread;   // 前驱线索
      p->leftChild = rec; // 左孩子指针指向前驱
    }
    if ( rec != NULL&& rec->rightChild != NULL) // 没有右孩子
    {
      rec->rTag = Thread;  // 后继线索
      rec->rightChild = p; // 前驱右孩子指针指向后继（当前节点p）
    }
    rec = p;
    inThread(p->rightChild); // 递归右子树线索化
  }
}
bool MyTree::inOrderThreading() // 线索化
{
  isThread = 1;
  inThread(root);
}
TreeNode &MyTree::locateNode(const char &v) // 结点定位
{
  stack<TreeNode *> s;
  TreeNode *p = root;
  while (p != NULL || !s.empty())
  {
    while (p != NULL)
    {
      if (p->data == v)
      {
        return *p;
      }
      s.push(p);
      p = p->leftChild; //???
    }
    if (!s.empty())
    {
      p = s.top();
      s.pop();
      p = p->rightChild; //???
    }
  }
}
TreeNode &MyTree::preNode(const TreeNode &v) // 获取前驱结点
{
  int i = ino.find(v.data);
  Node->data = ino[i - 1];
  return *Node;
}
TreeNode &MyTree::nextNode(const TreeNode &v) // 获取后继结点
{
  int i = ino.find(v.data);
  Node->data = ino[i + 1];
  return *Node;
}
void TreeNode::printNode()
{
  cout << this->data;
}
HuffmanTree::HuffmanTree(const int &x, const int ch[]) // 构造函数
{
  n = x;
  m = 2 * n - 1;
  for (int i = 0; i < n; i++)
    t[i].w = ch[i];
  for (int i = 0; i < m; i++)
  {
    t[i].parent = -1;
    t[i].left = -1;
    t[i].right = -1;
  }
  int INF = 0x3f3f3f3f;
  int min1, min2, pos1, pos2;
  for (int i = n; i < m; i++)
  {
    min2 = min1 = INF;
    for (int j = 0; j < i; j++)
    {
      if (t[j].parent == -1)
      {
        if (t[j].w < min1)
        {
          pos2 = pos1;
          min2 = min1;
          pos1 = j;
          min1 = t[j].w;
        }
        else
        {
          if (t[j].w < min2)
          {
            pos2 = j;
            min2 = t[j].w;
          }
        }
      }
    }
    t[i].left = pos1;
    t[i].right = pos2;
    t[i].w = t[pos1].w + t[pos2].w;
    t[pos1].parent = i;
    t[pos2].parent = i;
  }
}

// 析构函数
HuffmanTree::~HuffmanTree() {}
// 按编码输出
void HuffmanTree::printHuffmanCodes()
{
  int maxn = 0, pos = 0;
  for (int i = 1; i <= n; i++)
  {
    maxn = 0;
    for (int j = 0; j < n; j++)
    {
      if (t[j].w > maxn)
      {
        maxn = t[j].w;
        pos = j;
      }
    }
    t[pos].w = -1;
    int pos1;
    string s;
    while (t[pos].parent != -1)
    {
      pos1 = t[pos].parent;
      if (t[pos1].left == pos)
        s = '0' + s;
      else
        s = '1' + s;
      pos = pos1;
    }
    cout << maxn << ":" << s << endl;
  }
  return;
}
int main()
{
  // 树的构造
  MyTree t1("ABDG@@HJ@@K@@@CE@@F@I@@");

  // 前序遍历
  t1.preOrderTraverse(); // ABDGHJKCEFI
  cout << endl;

  // 中序遍历
  t1.inOrderTraverse(); // GDJHKBAECFI
  cout << endl;

  // 后序遍历
  t1.postOrderTraverse(); // GJKHDBEIFCA
  cout << endl;

  // 叶子节点个数
  cout << t1.countLeaf() << endl; // 5

  // 深度
  cout << t1.countHeight() << endl; // 5

  // 寻找树中节点
  TreeNode n1 = t1.locateNode('I');
  n1.printNode(); // I
  cout << endl;

  // 树的构造
  MyTree t2("ABC@D@E@@@@");

  // 前序遍历
  t2.preOrderTraverse(); // ABCDE
  cout << endl;

  // 中序遍历
  t2.inOrderTraverse(); // CDEBA
  cout << endl;

  // 后序遍历
  t2.postOrderTraverse(); // EDCBA
  cout << endl;

  // 叶子节点个数
  cout << t2.countLeaf() << endl; // 1

  // 深度
  cout << t2.countHeight() << endl; // 5

  // 线索化树
  MyTree t3(t1);
  t3.inOrderThreading();
  cout << t2.isThreadedTree() << endl; // 0
  cout << t3.isThreadedTree() << endl; // 1

  // 线索化树寻找前后结点
  TreeNode n2 = t3.locateNode('A');
  TreeNode n3 = t3.preNode(n2);
  TreeNode n4 = t3.nextNode(n2);

  n3.printNode(); // B
  cout << endl;
  n4.printNode(); // E
  cout << endl;

  TreeNode n5 = t3.locateNode('K');
  TreeNode n6 = t3.preNode(t3.preNode(n5));
  // 提示：若此处跨头结点会发生什么？

  n6.printNode(); // J
  cout << endl;

  // 霍夫曼树
  int nodes[6] = {3, 7, 30, 1, 16};
  HuffmanTree t4(5, nodes);
  t4.printHuffmanCodes();

  /*
      30:1
      16:01
      7:001
      3:0001
      1:0000
  */
  system("pause");
  return 0;
}